#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
char chos;
int input;
bool unbalanced = false;
struct node{
    int data;
    int bf;
    struct node *lchild;
    struct node *rchild;
};
typedef struct node *BST;
BST R = NULL;
 
void Chose(){
    printf("i) Insert a point\n"
           "d) Delete a point\n"
           "e) exit\n"
           "Input your choose:");
    scanf(" %c", &chos);
}

int Height(BST T){     /*返回当前节点的高度*/
    if(T == NULL)
        return -1;
    else
        return T->bf;
}

int Max(int A, int B){
    return ((A > B) ? A:B);
}

BST SingleRotateWithRight(BST K2){          /*RR型旋转*/
    BST K1;
    K1 = K2->rchild;
    K2->rchild = K1->lchild;
    K1->lchild = K2;
    K2->bf = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->bf = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
    return K1;
}

BST SingleRotateWithLeft(BST K2){           /*LL型旋转*/
    BST K1;
    K1 = K2->lchild;
    K2->lchild = K1->rchild;
    K1->rchild = K2;
    K2->bf = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->bf = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
    return K1;
}

BST DoubleRotateWithLeft(BST K3){           /*LR = RR(K3->lchild) + LL（K3）*/
    K3->lchild = SingleRotateWithRight(K3->lchild);
    return SingleRotateWithLeft(K3);
}

BST DoubleRotateWithRight(BST K3){          /*LL = LL(K3->lchild) + RR(K3)*/
    K3->rchild = SingleRotateWithLeft(K3->rchild);
    return SingleRotateWithRight(K3);
}

void OUT(BST T){                /*树的输出递归函数*/
    if(T->lchild){
        printf("Left\t%d\t[parent:%d]\n", T->lchild->data, T->data);
        OUT(T->lchild);
    }
    if(T->rchild){
        printf("Right\t%d\t[parent:%d]\n", T->rchild->data, T->data);
        OUT(T->rchild);
    }
}

BST Rotate(BST T){              /*对于单个节点进行的AVL调整*/
    if(Height(T->lchild) - Height(T->rchild) == 2){
        if(Height(T->lchild->lchild) >= Height(T->lchild->rchild)){
            T = SingleRotateWithLeft(T);
        }
        else{
            T = DoubleRotateWithLeft(T);
        }
    }
    if(Height(T->rchild) - Height(T->lchild) ==2){
        if(Height(T->rchild->rchild) >= Height(T->rchild->lchild)){
            T = SingleRotateWithRight(T);
        }
        else{
            T = DoubleRotateWithRight(T);
        }
    }
    return T;
}

BST AVLInsert(BST T){           /*AVL数的插入操作*/
    if(T == NULL){
        T = (BST)malloc(sizeof(struct node));
        T->data = input;
        T->lchild = T->rchild = NULL;
        T->bf = 0;
    }
    else if(input < T->data){
        T->lchild = AVLInsert(T->lchild);
        if(Height(T->lchild) - Height(T->rchild) == 2){
            if(input < T->lchild->data){
                T = SingleRotateWithLeft(T);            /*LL旋转*/
            }
            else{
                T = DoubleRotateWithLeft(T);            /*LR旋转*/
            }
        }
    }
    else if(input > T->data){
        T->rchild = AVLInsert(T->rchild);
        if(Height(T->rchild) - Height(T->lchild) == 2){
            if(input > T->rchild->data){
                T = SingleRotateWithRight(T);           /*RR旋转*/
            }
            else{
                T = DoubleRotateWithRight(T);           /*RL旋转*/
            }
        }
    }
    T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1;
    return T;
}

void Output(BST T){
    if(T == NULL){
        printf("None\n");
    }
    else{
        printf("%d\troot\n", T->data);
        OUT(T);
    }
}

void Insert(){
    printf("\nInput the point your want to Insert: ");
    scanf("%d", &input);
    R = AVLInsert(R);
    Output(R);
}

BST AVLDelete(BST T, int key){
    if(T == NULL)
        return NULL;
    if(key == T->data){
        if(T->rchild == NULL){          /*如果T得右儿子为空则直接删除*/
            BST temp = T;
            T = T->lchild;
            free(temp);
        }
        else{                           /*否则找到T->rchild的最左儿子代替T*/
            BST temp = T->rchild;
            while(temp->lchild != NULL){
                temp = temp->lchild;
            }
            T->data = temp->data;
            T->rchild = AVLDelete(T->rchild, temp->data);      /*对于替代后的T及其各个子节点进行一些列调整，正到再次递归到T->rchild的最左儿子，删除它*/
            T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1;
        }
        return T;
    }
    else if(key < T->data){
        T->lchild = AVLDelete(T->lchild, key);
    }
    else{
        T->rchild = AVLDelete(T->rchild, key);
    }
    T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1;
    if(T->lchild != NULL){
        T->lchild = Rotate(T->lchild);
    }
    if(T->rchild != NULL){
        T->rchild = Rotate(T->rchild);
    }
    T = Rotate(T);
    return T;
}

void Delete(){
    printf("\nInput the point you want to Delete: ");
    scanf("%d", &input);
    R = AVLDelete(R, input);
    Output(R);
}

int main(){
    while(1){
        Chose();
        switch(chos){
            case 'i':
                Insert();
                break;
            case 'd':
                Delete();
                break;
            case 'e':
                exit(0);
        }
    }
    return 0;
}
